package Simple;
import java.util.Stack;

/**
 * Input a linkedlist, reverse it in parts, like input 1,2,3,4,5 and pair=2
 * after reversing, it will be 2,1,4,3,5
 * @author CY
 *
 */
public class ReverseLinkedListInParts {
	Node head;
	int size;

	class Node {
		int value;
		Node next;

		public Node(int value) {
			super();
			this.value = value;
			this.next = null;
		}
	}

	public ReverseLinkedListInParts() {
		super();
		head = null;
		size = 0;
	}

	public void add(int e) {
		Node newnode = new Node(e);
		if (head == null) {
			head = newnode;
			size++;
			return;
		}
		Node ptr = head;
		while (ptr.next != null) {
			ptr = ptr.next;
		}
		ptr.next = newnode;
		size++;
	}

	public Node reverseInPart(int parts) {
		if (parts > size || parts < 1) {
			System.out.println("The part is out of range. Cannot reverse");
			return head;
		}
		Node begin = new Node(0);
		begin.next = head;
		Node pre = begin;
		int i=0;
		while(head!=null){
			i++;
			if(i%parts ==0){
				pre = reverse(pre, head.next);
				head = pre.next;
			}
			else{
				head = head.next;
			}
		}
		return begin.next;
	}

	private Node reverse(Node pre, Node tail) {
		Node old_pre_next = pre.next;
		Node cur = old_pre_next.next;
		while(cur!=tail){
			old_pre_next.next = cur.next;
			cur.next = pre.next;
			pre.next = cur;
			cur = old_pre_next.next;
		}
		return old_pre_next;
//		Node cur = pre.next;
//		Node oldtail = tail;
//		Node ret = pre.next;
//		while(cur.next!=oldtail){
//			pre.next = cur.next;
//			cur.next = tail;
//			tail = cur;
//			cur = pre.next;
//		}
//		cur.next = tail;
//		return ret;
	}

	public void print(int parts) {
		Node ptr = reverseInPart(parts);
		while (ptr != null) {
			System.out.print(ptr.value + ",");
			ptr = ptr.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		ReverseLinkedListInParts test = new ReverseLinkedListInParts();
		test.add(1);
		test.add(2);
		test.add(3);
		test.add(4);
		test.add(5);
		test.add(6);
		test.add(7);
//		test.print(1);
		test.print(3);
	}

}